560. 和为 K 的子数组

Similar Question

leading to the advanced question

Solution Tips

方案一: 暴力法 + 前缀和

var subarraySum = function(nums, k) {
    // 就看要不要排序了, 排序之后可以剪枝
    // 不排序的话就是 O n^2
    // 插入虚拟头, 避免特判? 好像不太能避免的样子
    // 前缀和有好多重复计算的地方, 怎么优化呢? 应该是可以用哈希表优化一下的
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        let prefixSum = 0;
        for (let j = i; j < nums.length; j++) {
            prefixSum += nums[j];
            if (prefixSum === k) {
                res++
            }
        }
    }

    return res;
};

let nums = [1,1,1], k = 2
console.log(subarraySum(nums, k));

方案二: 前缀和 + 哈希表

重点其实是寻找满足 pre[i] - pre[j -1] = k 的 i 和 j, i 大于 j, 那么在一次遍历 i 的过程中就可以找出所有的 j 了

var subarraySum = function(nums, k) {
    const mp = new Map();
    mp.set(0, 1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if (mp.has(pre - k)) {
            count += mp.get(pre - k);
        }
        if (mp.has(pre)) {
            mp.set(pre, mp.get(pre) + 1);
        } else {
            mp.set(pre, 1);
        }
    }
    return count;
};